<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>dfs</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="dfs">dfs</h1>
<h1 id="1-lc-417-pacific-atlantic-water-flow">1. LC 417 Pacific Atlantic Water Flow</h1>
<ul>
<li><a href="https://leetcode.com/problems/pacific-atlantic-water-flow/">https://leetcode.com/problems/pacific-atlantic-water-flow/</a></li>
<li><a href="https://zhuanlan.zhihu.com/p/157904930">https://zhuanlan.zhihu.com/p/157904930</a></li>
</ul>
<h1 id="2-lc-1020-飞地的数量">2. LC 1020 飞地的数量</h1>
<ul>
<li><a href="https://leetcode.com/problems/number-of-enclaves/">https://leetcode.com/problems/number-of-enclaves/</a></li>
<li><a href="https://zhuanlan.zhihu.com/p/152602846">https://zhuanlan.zhihu.com/p/152602846</a></li>
</ul>
<h1 id="3-lc-490-the-maze">3. LC 490 The Maze</h1>
<ul>
<li><a href="https://leetcode.com/problems/the-maze/">https://leetcode.com/problems/the-maze/</a></li>
</ul>
<p>There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.</p>
<p>Given the maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.</p>
<p>You may assume that the borders of the maze are all walls (see examples).</p>
<pre><code><code><div>Example 1:


Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -&gt; down -&gt; left -&gt; down -&gt; right -&gt; down -&gt; right.
</div></code></code></pre>
<p>本地用dfs或者bfs都行，但是需要一些特殊的处理。很难第一次就写对</p>
<h2 id="dfs-1">DFS</h2>
<p>我最开始的解法，搞复杂了</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">hasPath</span><span class="hljs-params">(self, maze: List[List[int]], start: List[int], destination: List[int])</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> maze <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> maze[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        m = len(maze)
        n = len(maze[<span class="hljs-number">0</span>])
        <span class="hljs-comment">#print(f"m={m} n={n}")</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(x, y, dx, dy, visited)</span>:</span>            
            <span class="hljs-keyword">while</span> <span class="hljs-literal">True</span>:
                x2, y2 = x+dx, y+dy            
                <span class="hljs-keyword">if</span> x2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> x2 &gt;=m <span class="hljs-keyword">or</span> y2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> y2 &gt;= n <span class="hljs-keyword">or</span> maze[x2][y2] == <span class="hljs-number">1</span>:
                    <span class="hljs-keyword">break</span>
                x, y = x2, y2
            
            <span class="hljs-comment">#rint(f"  x={x} y={y}")</span>
            <span class="hljs-keyword">if</span> x == destination[<span class="hljs-number">0</span>] <span class="hljs-keyword">and</span> y == destination[<span class="hljs-number">1</span>]:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            
           
            <span class="hljs-keyword">if</span> (x, y) <span class="hljs-keyword">in</span> visited:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
            visited[(x, y)] = <span class="hljs-number">1</span>
            
            <span class="hljs-keyword">for</span> dx2, dy2 <span class="hljs-keyword">in</span> [(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>), (<span class="hljs-number">0</span>, <span class="hljs-number">-1</span>), (<span class="hljs-number">1</span>, <span class="hljs-number">0</span>), (<span class="hljs-number">-1</span>, <span class="hljs-number">0</span>)]:
                x2, y2 = x+dx2, y+dy2
                <span class="hljs-keyword">if</span> x2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> x2 &gt;=m <span class="hljs-keyword">or</span> y2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> y2 &gt;= n <span class="hljs-keyword">or</span> maze[x2][y2] == <span class="hljs-number">1</span>:
                    <span class="hljs-keyword">continue</span>
                
                r = dfs(x2, y2, dx2, dy2, visited)
                <span class="hljs-keyword">if</span> r:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
       
         
        <span class="hljs-keyword">for</span> dx, dy <span class="hljs-keyword">in</span> [(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>), (<span class="hljs-number">0</span>, <span class="hljs-number">-1</span>), (<span class="hljs-number">1</span>, <span class="hljs-number">0</span>), (<span class="hljs-number">-1</span>, <span class="hljs-number">0</span>)]:
            x2, y2 = start[<span class="hljs-number">0</span>]+dx, start[<span class="hljs-number">1</span>]+dy
            <span class="hljs-keyword">if</span> x2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> x2 &gt;=m <span class="hljs-keyword">or</span> y2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> y2 &gt;= n <span class="hljs-keyword">or</span> maze[x2][y2] == <span class="hljs-number">1</span>:
                <span class="hljs-keyword">continue</span>
            r = dfs(start[<span class="hljs-number">0</span>], start[<span class="hljs-number">1</span>], dx, dy, {(start[<span class="hljs-number">0</span>], start[<span class="hljs-number">1</span>]):<span class="hljs-number">1</span>} )
            <span class="hljs-keyword">if</span> r:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
</div></code></pre>
<p>看了官方答案以后的解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">hasPath</span><span class="hljs-params">(self, maze: List[List[int]], start: List[int], destination: List[int])</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> maze <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> maze[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        m = len(maze)
        n = len(maze[<span class="hljs-number">0</span>])
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(x, y, visited)</span>:</span>
            <span class="hljs-comment">#print(f"x={x} y={y}")</span>
            <span class="hljs-keyword">if</span> x == destination[<span class="hljs-number">0</span>] <span class="hljs-keyword">and</span> y == destination[<span class="hljs-number">1</span>]:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">if</span> (x,y) <span class="hljs-keyword">in</span> visited:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
            visited[(x, y)] = <span class="hljs-number">1</span>
            
            <span class="hljs-keyword">for</span> dx2, dy2 <span class="hljs-keyword">in</span> [(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>), (<span class="hljs-number">0</span>, <span class="hljs-number">-1</span>), (<span class="hljs-number">1</span>, <span class="hljs-number">0</span>), (<span class="hljs-number">-1</span>, <span class="hljs-number">0</span>)]:
                x2, y2 = x+dx2, y+dy2
                <span class="hljs-comment"># 首先判断这个方向能否走。这里必须用x2, y2, 要保留原始的x, y变量</span>
                <span class="hljs-keyword">if</span> x2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> x2 &gt;=m <span class="hljs-keyword">or</span> y2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> y2 &gt;= n <span class="hljs-keyword">or</span> maze[x2][y2] == <span class="hljs-number">1</span>:
                    <span class="hljs-keyword">continue</span>
            
                <span class="hljs-comment"># 如果能走，就往一个方向走到头。</span>
                <span class="hljs-keyword">while</span> x2 &gt;= <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> x2 &lt; m <span class="hljs-keyword">and</span> y2 &gt;= <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> y2 &lt; n <span class="hljs-keyword">and</span> maze[x2][y2] == <span class="hljs-number">0</span>:
                    x2, y2 = x2+dx2, y2+dy2
                
                r = dfs(x2-dx2, y2-dy2, visited)
                <span class="hljs-keyword">if</span> r:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
                
        <span class="hljs-keyword">return</span> dfs(start[<span class="hljs-number">0</span>], start[<span class="hljs-number">1</span>], {})
                   
</div></code></pre>
<h2 id="bfs">bfs</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">hasPath</span><span class="hljs-params">(self, maze: List[List[int]], start: List[int], destination: List[int])</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> maze <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> maze[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        m = len(maze)
        n = len(maze[<span class="hljs-number">0</span>])
        
        queue = [(start[<span class="hljs-number">0</span>], start[<span class="hljs-number">1</span>])]
        visited = {}
        
        <span class="hljs-keyword">while</span> queue:
            x, y = queue.pop(<span class="hljs-number">0</span>)
            <span class="hljs-keyword">if</span> x == destination[<span class="hljs-number">0</span>] <span class="hljs-keyword">and</span> y == destination[<span class="hljs-number">1</span>]:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">if</span> (x,y) <span class="hljs-keyword">in</span> visited:
                <span class="hljs-keyword">continue</span>
            visited[(x, y)] = <span class="hljs-number">1</span>
            
            <span class="hljs-keyword">for</span> dx2, dy2 <span class="hljs-keyword">in</span> [(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>), (<span class="hljs-number">0</span>, <span class="hljs-number">-1</span>), (<span class="hljs-number">1</span>, <span class="hljs-number">0</span>), (<span class="hljs-number">-1</span>, <span class="hljs-number">0</span>)]:
                x2, y2 = x+dx2, y+dy2
                <span class="hljs-comment"># 首先判断这个方向能否走。这里必须用x2, y2, 要保留原始的x, y变量</span>
                <span class="hljs-keyword">if</span> x2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> x2 &gt;=m <span class="hljs-keyword">or</span> y2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> y2 &gt;= n <span class="hljs-keyword">or</span> maze[x2][y2] == <span class="hljs-number">1</span>:
                    <span class="hljs-keyword">continue</span>
            
                <span class="hljs-comment"># 如果能走，就往一个方向走到头。</span>
                <span class="hljs-keyword">while</span> x2 &gt;= <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> x2 &lt; m <span class="hljs-keyword">and</span> y2 &gt;= <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> y2 &lt; n <span class="hljs-keyword">and</span> maze[x2][y2] == <span class="hljs-number">0</span>:
                    x2, y2 = x2+dx2, y2+dy2
                
                queue.append((x2-dx2, y2-dy2))
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
                
</div></code></pre>
<p>另一种bfs, 唯一的区别是什么时候，设置visited</p>
<ol>
<li>上面一种解法里面，是在访问具体节点的时候，设置visited</li>
<li>下面这种解法里面，是在把node添加到queue的时候，就设置visited.</li>
</ol>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">hasPath</span><span class="hljs-params">(self, maze: List[List[int]], start: List[int], destination: List[int])</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> maze <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> maze[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        m = len(maze)
        n = len(maze[<span class="hljs-number">0</span>])
        
        queue = [(start[<span class="hljs-number">0</span>], start[<span class="hljs-number">1</span>])]
        visited = {(start[<span class="hljs-number">0</span>], start[<span class="hljs-number">1</span>]):<span class="hljs-number">1</span>}  <span class="hljs-comment"># 设置visited初始值</span>
        
        <span class="hljs-keyword">while</span> queue:
            x, y = queue.pop(<span class="hljs-number">0</span>)
            <span class="hljs-comment">#print(f"x={x} y={y} queue={queue}")</span>
            <span class="hljs-keyword">if</span> x == destination[<span class="hljs-number">0</span>] <span class="hljs-keyword">and</span> y == destination[<span class="hljs-number">1</span>]:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            
            <span class="hljs-keyword">for</span> dx2, dy2 <span class="hljs-keyword">in</span> [(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>), (<span class="hljs-number">0</span>, <span class="hljs-number">-1</span>), (<span class="hljs-number">1</span>, <span class="hljs-number">0</span>), (<span class="hljs-number">-1</span>, <span class="hljs-number">0</span>)]:
                x2, y2 = x+dx2, y+dy2
                <span class="hljs-comment"># 首先判断这个方向能否走。这里必须用x2, y2, 要保留原始的x, y变量</span>
                <span class="hljs-keyword">if</span> x2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> x2 &gt;=m <span class="hljs-keyword">or</span> y2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> y2 &gt;= n <span class="hljs-keyword">or</span> maze[x2][y2] == <span class="hljs-number">1</span>:
                    <span class="hljs-keyword">continue</span>
            
                <span class="hljs-comment"># 如果能走，就往一个方向走到头。</span>
                <span class="hljs-keyword">while</span> x2 &gt;= <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> x2 &lt; m <span class="hljs-keyword">and</span> y2 &gt;= <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> y2 &lt; n <span class="hljs-keyword">and</span> maze[x2][y2] == <span class="hljs-number">0</span>:
                    x2, y2 = x2+dx2, y2+dy2
                
                <span class="hljs-keyword">if</span> (x2-dx2, y2-dy2) <span class="hljs-keyword">in</span> visited:  <span class="hljs-comment"># 添加到queue之前，就设置visited.</span>
                    <span class="hljs-keyword">continue</span>
                visited[(x2-dx2, y2-dy2)] = <span class="hljs-number">1</span>
                queue.append((x2-dx2, y2-dy2))
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
                     
            
</div></code></pre>
<h1 id="4-lc-489-robot-room-cleaner-向量变换矩阵值得借鉴">4 LC 489. Robot Room Cleaner, 向量变换矩阵值得借鉴</h1>
<ul>
<li><a href="https://leetcode.com/problems/robot-room-cleaner/">https://leetcode.com/problems/robot-room-cleaner/</a></li>
</ul>
<p>一个扫地机器人，给定了4个方法。 在不了解房间具体情况下，设计算法，能把所有地面都清理掉。</p>
<ul>
<li>move()</li>
<li>clean()</li>
<li>turnLeft()</li>
<li>turnRight()</li>
</ul>
<p>还是dfs,  暴力遍历，不管机器人实际坐标，和实际方向是什么。 就假设自己的初始坐标是(0, 0), 初始方向是向右. 每到一个新的位置，都把4个方向都dfs一遍。 一共4个方向</p>
<pre><code> 上，   左，     下，     右
[(0,1), (-1, 0), (0, -1), (1, 0)]
</code></pre>
<p>我们按照逆时针方向turnLeft()遍历， 有向量变化矩阵</p>
<pre><code>[x, y] * [0 , 1] =  [-y, x]
         [-1, 0]

这就是后面为什么  dx, dy = -dy, dx
</code></pre>
<p>当然，也可以按照顺时针turnRight()扫描， 有向量变化矩阵</p>
<pre><code>[x, y] * [0 , -1] =  [y, -x]
         [1, 0]
</code></pre>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">cleanRoom</span><span class="hljs-params">(self, robot)</span>:</span>
        <span class="hljs-string">"""
        :type robot: Robot
        :rtype: None
        """</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(x, y, dx, dy)</span>:</span>
            robot.clean()
            visited[(x, y)] = <span class="hljs-number">1</span>
            
            <span class="hljs-comment">#for dx2, dy2 in [(0,1), (-1, 0), (0, -1), (1, 0)]:</span>
            <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(<span class="hljs-number">4</span>):
                x2, y2 = x + dx, y + dy
                <span class="hljs-keyword">if</span> (x2, y2) <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> visited <span class="hljs-keyword">and</span> robot.move():
                    dfs(x2, y2, dx, dy)
                    robot.turnLeft()  <span class="hljs-comment"># 下面的5个步骤是为了goback回到原来的位置。再继续扫描另一个方向</span>
                    robot.turnLeft()
                    robot.move()
                    robot.turnLeft()
                    robot.turnLeft()
                robot.turnLeft()   <span class="hljs-comment"># goback 以后， 按照anti-clockwise 切换方向</span>
                dx, dy = -dy, dx <span class="hljs-comment"># </span>
        visited = {}
        dfs(<span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">1</span>)
</div></code></pre>
<p>另一个解法，是按照顺时针扫描的，而且对visited的处理有点区别</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">cleanRoom</span><span class="hljs-params">(self, robot)</span>:</span>
        <span class="hljs-string">"""
        :type robot: Robot
        :rtype: None
        """</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(x, y, dx, dy)</span>:</span>
            <span class="hljs-keyword">if</span> (x, y) <span class="hljs-keyword">in</span> visited:
                <span class="hljs-keyword">return</span>
            visited.add((x,y))
            robot.clean()
            
            <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(<span class="hljs-number">4</span>):
                x2, y2 = x + dx, y + dy
                <span class="hljs-keyword">if</span> robot.move():
                    dfs(x2, y2, dx, dy)
                    robot.turnRight()
                    robot.turnRight()
                    robot.move()
                    robot.turnRight()
                    robot.turnRight()
                robot.turnRight()
                dx, dy = dy, -dx
                
        visited = set()
        dfs(<span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">1</span>)
</div></code></pre>

    </body>
    </html>